/* 
  1 使用带有头尾指针的链表实现一个队列
  在链表头删除元素，链表尾添加元素
  这时因为链表尾删除元素的时间复杂度还是O(1)
*/
class Node {
  constructor(data, next) {
    this.data = data;
    this.next = next;
  }
}
class LinkedListQueue {
  constructor() {
    this.size = 0;
    this.head = null;
    this.tail = null;
  }

  getSize() {
    return this.size;
  }

  isEmpty() {
    return this.size === 0;
  }

  enqueue(data) {
    if (this.tail === null) {
      this.tail = new Node(data);
      this.head = this.tail;
    } else {
      this.tail.next = new Node(data);
      this.tail = this.tail.next;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error('queue isEmpty!!!');
    }
    const delNode = this.head;
    this.head = delNode.next;
    delNode.next = null;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return delNode.data;
  }
}

const queue = new LinkedListQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 1 2 3
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
